package main.java.indi.zyj.coderecord;

import java.util.Stack;

public class Trap {




    public int trap(int[] height) {

        int len = height.length;
        if (len < 3) {
            return 0;
        }

        Stack<Integer> stack = new Stack<>();
        int res = 0;
        stack.push(0);

        for (int i = 1; i < len; i++) {

            int topNum = height[stack.peek()];

            if (topNum == height[i]) {
                stack.pop();
                stack.push(i);
            } else if (topNum > height[i]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && height[i] > topNum) {
                    int mid = stack.pop();
                    if (!stack.isEmpty()) {
                        int left = stack.peek();
                        int h = Math.min(height[left], height[i]) - height[mid];
                        int w = i - left - 1;
                        int hold = h * w;
                        if (hold > 0) res += hold;
                        topNum = height[stack.peek()];
                    }
                }
                stack.push(i);
            }
        }
        return res;
    }

    public int trap1(int[] height) {

        int left = 0, right = height.length - 1, maxLeft = 0, maxRight = 0, res = 0;

        while (left < right) {
            maxLeft = Math.max(height[left], maxLeft);
            maxRight = Math.max(height[right], maxRight);
            res += maxLeft > maxRight ? maxRight - height[right--] : maxLeft - height[left++];
        }

        return res;

    }

}